#include <iostream>
#include <vector>
#include <set>

using namespace std;

#ifndef __NODO
#define __NODO

class Nodo {
public:

    Nodo() {
        this->id = -1;
        this->color = -1;
        this-> grado = 0;
        this-> gradoSaturacion = 0;
        this->adyacentes.clear();
    };

    Nodo(int id) {
        this->id = id;
        this->color = -1;
        this->grado = 0;
        this->gradoSaturacion = 0;
        this->adyacentes.clear();
    };

    //    /** Constructor chimbo, deberia clonar a orig
    //     * 
    //     * @param orig
    //     */
    //    Nodo(const Nodo& orig){
    //    };

    /** Destructor (no destruye nada)
     * 
     */
    virtual ~Nodo() {

    };
    
    // Getters y Setters

    vector<Nodo*> getAdyacentes() const {
        return adyacentes;
    }

    void setAdyacentes(vector<Nodo*> adyacentes) {
        this->adyacentes = adyacentes;
    }

    int getColor() const {
        return color;
    }

    void setColor(int color) {
        this->color = color;
    }

    int getGrado() const {
        return grado;
    }

    void setGrado(int grado) {
        this->grado = grado;
    }

    int getGradoSaturacion() const {
        return gradoSaturacion;
    }

    void setGradoSaturacion(int gradoSaturacion) {
        this->gradoSaturacion = gradoSaturacion;
    }

    int getId() const {
        return id;
    }

    void setId(int id) {
        this->id = id;
    }

    /** Agrega n como nodo adyacente de this ssi no existe previamente y
     * es diferente de this. La comparacion se hace mediante el operador ==
     * 
     * @param n Referencia al nodo que se desea insertar como adyacente
     * @return true si lo agrega, false si no.
     */
    bool agregarAdyacente(Nodo * n) {
        // cout << "Agregando a " << this->id << " el nodo adyacente: " << n->id << endl;
        if (*this == *n) { // No admite bucles
            return false;
        }
        // Busca por nodos repetidos
        for (vector<Nodo*>::iterator i = this->adyacentes.begin();
                i != this->adyacentes.end(); i++) {
            if (*n == **i) {
                return false;
            }
        }
        this->adyacentes.push_back(n);
        this->grado++;
        //        this->imprimirAdyacentes();
        return true;
    }
    
    /** Borra de la lista de nodos adyacentes de this el nodo que evalue true
     * al compararlo usando == con el nodo n. Si ninguno evalua true, no se modifica
     * la lista.
     * 
     * @param n Nodo que se desea eliminar.
     */
    void eliminarAdyacente(Nodo * n) {
        for (vector<Nodo*>::iterator i = this->adyacentes.begin();
                i != this->adyacentes.end(); i++) {
            if (*n == **i) {
                adyacentes.erase(i);
                this->grado--;
                break;
            }
        }
    }

    /** 
     * 
     */
    void incrementarGradoSaturacion() {

        set<int> colores;

        for (int i = 0; i < this->adyacentes.size(); i++) {
            Nodo * a = this->adyacentes.at(i);
            for (int j = 0; j < a->getAdyacentes().size(); j++) {
                Nodo * b = a->getAdyacentes().at(j);
                int color = b->getColor();
                if (color != -1) {
                    colores.insert(b->getColor());
                }
            }
            a->setGradoSaturacion(colores.size());
            colores.clear();
        }

    }

    /** Consulta entre los nodos adyacentes a this cual es el menor color
     * que no aun no ha sido usado por ellos.
     * 
     * @return Un color factible para this
     */
    int encontrarMenorColor() {
        set<int> colores;
        for (vector<Nodo*>::iterator i = this->adyacentes.begin();
                i != this->adyacentes.end(); i++) {
            if((*i)->getColor() != -1)
              colores.insert((*i)->getColor());
        }
        int color = 1;
        for (set<int>::iterator i = colores.begin();
                i != colores.end(); i++) {
            if (color < *i)
                break;
            else
                color++;
        }
        return color;
    }

    void imprimirAdyacente() {
        for (vector<Nodo*>::iterator it = this->adyacentes.begin();
                it != this->adyacentes.end(); it++) {
            cout << (*it)->getId() << " ";
        }
    }

    bool operator==(const Nodo & n) const {
        return this->id == n.id;
    }

private:

    int id;
    int color;
    int grado;
    int gradoSaturacion;
    vector<Nodo*> adyacentes;

};

#endif